﻿// 0818train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 */
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

TreeNode* BuildNode(vector<int>&tree_vec)
{
    TreeNode* root_node = new TreeNode(tree_vec[0]);
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root_node);

    int index = 1;
    while (!bfs_queue.empty() && index<tree_vec.size())
    {
        TreeNode* curr_node = bfs_queue.front();
        bfs_queue.pop();

        if (index < tree_vec.size() && tree_vec[index]!=INT_MIN)
        {
            curr_node->left = new TreeNode(tree_vec[index]);
            bfs_queue.push(curr_node->left);
        }
        index++;

        if (index<tree_vec.size() && tree_vec[index]!=INT_MIN)
        {
            curr_node->right = new TreeNode(tree_vec[index]);
            bfs_queue.push(curr_node->right);
        }
        index++;

    }
    return root_node;
    //BuildNode
}

class Solution01 {
public:
    bool checked(TreeNode*origin_root, TreeNode*mirror_root)
    {
        queue<TreeNode*>bfs_queue;
        bfs_queue.push(origin_root);
        bfs_queue.push(mirror_root);

        while (!bfs_queue.empty())
        {
            TreeNode* origin_node = bfs_queue.front();
            bfs_queue.pop();
            TreeNode* mirror_node = bfs_queue.front();
            bfs_queue.pop();

            if (!origin_node && !mirror_node) continue;
            if ((!origin_node || !mirror_node)||(origin_node->val != mirror_node->val))
            {
                return false;
            }

            //注意这里的写法
            bfs_queue.push(origin_node->left);
            bfs_queue.push(mirror_node->right);

            bfs_queue.push(origin_node->right);
            bfs_queue.push(mirror_node->left);

        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        return checked(root, root);
    }
};


class Solution02 {
public:
    int deepestLeavesSum(TreeNode* root) {

        queue<TreeNode*>bfs_queue;
        bfs_queue.push(root);

        vector<vector<int>>level_vec;

        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();
            vector<int>curr_vec;
            for (int i=0; i<q_size; i++)
            {
                TreeNode* top_node = bfs_queue.front();
                bfs_queue.pop();

                curr_vec.push_back(top_node->val);
                if (top_node->left!=nullptr)
                {
                    bfs_queue.push(top_node->left);
                }
                if (top_node->right!=nullptr)
                {
                    bfs_queue.push(top_node->right);
                }
            }
            level_vec.push_back(curr_vec);

        }
        vector<int>last_level_vec = level_vec[level_vec.size() - 1];
        int sum = 0;
        for (auto&num:last_level_vec)
        {
            sum += num;
        }
        return sum;
    }
};


/*
输入描述
第一行为总人数N
第二行为确诊病例人员编号(确诊病例人员数量<N)，用逗号分割
第三行开始，为一个N*N的矩阵，表示每个人员之间是否有接触，0表示没有接触，1表示有接触。

输出描述
整数：需要做核酸检测的人数

输入
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1

输出
3
编号为1、2号的人员，为确诊病例。
1号和0号有接触，0号和3号有接触。
2号和4号有接触。
所以，需要做核酸检测的人是0号、3号、4号，总计3人需要进行核酸检测
 */
class Solution03
{
public:
    unordered_set<int>target_set;
    queue<int>bfs_queue;
    vector<int>result_vec;
    void solve03(vector<vector<int>>&grid, vector<int>&origin_target)
    {
        /*
         思路，拿一个map存，如果有接触就push到map的数组里
         */
        int grid_size = grid.size();
        vector<bool>checked(grid_size);
        for (auto&target_index:origin_target)
        {
            bfs_queue.push(target_index);
            checked[target_index] = true;
            //用于后面去重，已感染的不用做核酸
            target_set.insert(target_index);
        }

        while (!bfs_queue.empty())
        {
            //next_i!=curr_i 未访问 curr_vec[next_i]==1
            int curr_index = bfs_queue.front();
            bfs_queue.pop();
            result_vec.push_back(curr_index);

            vector<int>curr_vec = grid[curr_index];

            for (int next_i=0; next_i<grid_size; next_i++)
            {
                bool is_visited = checked[next_i];
                bool is_available = curr_vec[next_i] == 1;

                if (next_i!=curr_index && !is_visited && is_available)
                {
                    bfs_queue.push(next_i);
                    checked[next_i] = true;
                }

            }

        }

        int result = 0;
        for (auto&num:result_vec)
        {
            if (target_set.count(num) == 0)
                result += 1;
        }
        cout << result;
        //solve03------
    }

};

/*
 给你一个 n x n 的关联矩阵 isConnected ，其中 isConnected[i][j] = 1
 表示第 i 个发行版和第 j 个发行版直接关联，
 而 isConnected[i][j] = 0 表示二者不直接相连。
返回最大的发行版集中发行版的数量。

输入描述
第一行输入发行版的总数量 N，之后每行表示各发行版间是否直接相关。
输出描述
输出最大的发行版集中发行版的数量

输入
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
输出
3
 */

class Solution04
{
public:
    queue<int>bfs_queue;
    int result = 0;
    void solve04(vector<vector<int>>&grid)
    {
        int grid_size = grid.size();
        //checked bfs_queue
        vector<bool>checked(grid_size, false);

        //未访问加入bfs_queue
        //未访问 i!=curr_index curr_vec[i]==1

        for (int first_i=0; first_i <grid_size; first_i++)
        {
            //未访问加入bfs_queue
            if (!checked[first_i])
            {
                bfs_queue.push(first_i);
                //标识已访问
                checked[first_i] = true;

                int curr_count = 0;
                while (!bfs_queue.empty())
                {
                    curr_count++;
                    int curr_index = bfs_queue.front();
                    bfs_queue.pop();

                    vector<int>curr_vec = grid[curr_index];
                    for (int next_i=0; next_i<grid_size; next_i++)
                    {
                        bool is_visited = checked[next_i];
                        bool is_available = curr_vec[next_i] == 1;

                        if (next_i!=curr_index && !is_visited &&is_available)
                        {
                            bfs_queue.push(next_i);
                            //标识已访问
                            checked[next_i] = true;
                        }

                    }

                }
                result = max(result, curr_count);

            }
	        
        }

        cout << result;
	    
    }
};

/*
 给定一个m*n的整数阵作为地图，短阵数值为地形高度；
中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;
移动时有如下约束：
中庸行者只能上坡或者下坡，不能走到高度相同的点。
不允许连续上坡或者连续下坡，需要交替进行;
每个位置只能经过一次，不能重复行走；
请给出中庸行者在本地图内，能连续移动的最大次数
 */

class Solution05
{
public:
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
    int row_size, col_size;
    //可变区
    int max_step = 0;
    int curr_step = 0;
    vector<int>dir_z_vec; //上坡1，下坡-1

    vector<int>result_vec;
    vector<int>track_vec;

    bool checked_available(int curr_value, int prev_value)
    {
        if (curr_value == prev_value) return false;

        if (dir_z_vec.empty()) return true;

        int curr_z = curr_value > prev_value ? 1 : -1;
        if (curr_z!=dir_z_vec[dir_z_vec.size()-1])
        {
            return true;
        }
        return false;
    }

    void backTrack(vector<vector<int>>&grid, vector<vector<bool>>&checked, int prev_r,int prev_c)
    {
        if (curr_step>max_step)
        {
            result_vec = track_vec;
        }

    	max_step = max(max_step, curr_step);

        for (auto&dir_vec: DirectionGrid)
        {
            //未越界，未访问，不等于grid[prev_r][prev_c]
            int curr_r = prev_r + dir_vec[0];
            int curr_c = prev_c + dir_vec[1];

            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

            if (is_curr_r&&is_curr_c)
            {
                bool is_visited = checked[curr_r][curr_c];
                int curr_value = grid[curr_r][curr_c];
                int prev_value = grid[prev_r][prev_c];

                bool is_available = checked_available(curr_value, prev_value);
                
                if (!is_visited && is_available)
                {
                    //做选择
                    int curr_z = curr_value > prev_value ? 1 : -1;
                    dir_z_vec.push_back(curr_z);
                    checked[curr_r][curr_c] = true;
                    curr_step++;
                    track_vec.push_back(grid[curr_r][curr_c]);
                    //回溯
                    backTrack(grid, checked, curr_r, curr_c);
                    //撤销选择
                    dir_z_vec.pop_back();
                    checked[curr_r][curr_c] = false;
                    curr_step--;
                    track_vec.pop_back();
                }


            }


        }

    }

    void solve05(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        vector<bool>check_status(col_size, false);
        vector<vector<bool>>checked(row_size,check_status);

        for (int r=0;r<row_size;r++)
        {
            for (int c=0; c<col_size; c++)
            {
                //做选择
                checked[r][c] = true;
                curr_step++;
                track_vec.push_back(grid[r][c]);
                //回溯
                backTrack(grid, checked, r, c);
                //撤销选择
                checked[r][c] = false;
                curr_step--;
                track_vec.pop_back();
            }

        }
        //for (auto&num:result_vec)
        //{
        //    cout << num << ' ';
        //}

        cout << max_step-1;
        //solve05
    }

};


int main()
{
	{
/*
3 2
11 32
63 60
36 85
*/
        int row_size, col_size;
        cin >> row_size >> col_size;
        
        vector<vector<int>>grid(row_size,vector<int>(col_size));
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];
            }

        }

        //for (auto&inner_vec:grid)
        //{
	       // for (auto&num:inner_vec)
	       // {
        //        cout << num << ' ';
	       // }
        //    cout << '\n';
        //}

        //vector<int>vec1 = { 3,2 };
        //vector<int>vec2 = { 11,32 };
        //vector<int>vec3 = { 63,60 };
        //vector<int>vec4 = { 36,85 };
        //vector<vector<int>>grid = { vec1,vec2,vec3,vec4 };
        Solution05 solu;
        solu.solve05(grid);

        return 0;
	}
	{
        /*
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
         */
        int target_size;
        cin >> target_size;
        cin.ignore();

        string input;
        getline(cin, input);
        stringstream oh_sstream1(input);
        string token;
        vector<int>target_vec;
        while (getline(oh_sstream1,token,','))
        {
            target_vec.push_back(stoi(token));
        }

        vector<vector<int>>grid;
        for (int i=0; i<target_size;i++)
        {
            getline(cin, input);
            stringstream oh_sstream2(input);
            vector<int>curr_vec;
            while (getline(oh_sstream2,token,','))
            {
                curr_vec.push_back(stoi(token));
            }
            grid.push_back(curr_vec);
        }

        //for (auto&inner_vec:grid)
        //{
	       // for (auto&num:inner_vec)
	       // {
        //        cout << num << ' ';
	       // }
        //    cout << '\n';
        //}
        
        //vector<int>vec1 = { 1,1,0,1,0 };
        //vector<int>vec2 = { 1,1,0,0,0 };
        //vector<int>vec3 = { 0,0,1,0,1 };
        //vector<int>vec4 = { 1,0,0,1,0 };
        //vector<int>vec5 = { 0,0,1,0,1 };

        //vector<vector<int>>grid = { vec1 ,vec2,vec3,vec4,vec5 };
        //vector<int>target_vec = { 1,2 };

        Solution03 solu;
        solu.solve03(grid, target_vec);

        return 0;
	}

	{
/*
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
*/
        int grid_size;
        cin >> grid_size;

        vector<vector<int>>grid(grid_size,vector<int>(grid_size));
        for (int r=0; r<grid_size; r++)
        {
            for (int c=0; c<grid_size; c++)
            {
                cin >> grid[r][c];
            }

        }

        //vector<int>vec1 = { 1,1,0,0 };
        //vector<int>vec2 = { 1,1,1,0 };
        //vector<int>vec3 = { 0,1,1,0 };
        //vector<int>vec4 = { 0,0,0,1 };
        //vector<vector<int>>grid = { vec1,vec2,vec3,vec4 };

        Solution04 solu;
        solu.solve04(grid);

        return 0;
	}

    //root = [1,2,2,3,4,4,3]
    //vector<int>tree_vec = { 1,2,2,3,4,4,3 };
    //TreeNode* root = BuildNode(tree_vec);
    //Solution01 solu;
    //cout << solu.isSymmetric(root);
    const int null = INT_MIN;
    vector<int>tree_vec = { 1,2,3,4,5,null,6,7,null,null,null,null,8 };

    TreeNode* root = BuildNode(tree_vec);
    Solution02 solu;
    cout << solu.deepestLeavesSum(root);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
